public class text {
    解题思路:
            1. 从后往前遍历数组，将nums1和nums2中的元素逐个比较
            将较大的元素往nums1末尾进行搬移
      2. 第一步结束后，nums2中可能会有数据没有搬移完，将nums2中剩余的元素逐个搬移到nums1

   ﻿时间复杂度：O(m+n)
    空间复杂度: O(1)
*/
    class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            // end1、end2：分别标记nums1 和 nums2最后一个有效元素位置
            // end标记nums1的末尾，因为nums1和nums2中的元素从后往前往nums1中存放
            // ，否则会存在数据覆盖
            int end1 = m-1;
            int end2 = n-1;
            int end = nums1.length-1;

            // 从后往前遍历，将num1或者nums2中较大的元素往num1中end位置搬移
            // 直到将num1或者num2中有效元素全部搬移完
            while(end1 >= 0 && end2 >= 0){
                if(nums1[end1] > nums2[end2]){
                    nums1[end--] = nums1[end1--];
                }else{
                    nums1[end--] = nums2[end2--];
                }
            }

            // 如果nums2中的数据没有搬移完，搬移剩余nums中的元素
            while(end2 >= 0){
                nums1[end--] = nums2[end2--];
            }

            // num1中可能有数据没有搬移完，不用管，因为这些元素已经在nums1中了
        }
    }


























    解题思路：
            1. 设置一个计数，记录从前往后遍历时遇到的不同元素的个数
    由于不同的元素需要往前搬移，那count-1就是前面不同元素
    搬移之后，最后一个元素的位置，下一次在遇到不同元素就应该
            搬移到count位置
       2. 遍历数组，如果nums[i]与nums[count-1]不等，就将nums[i]搬移
    到nums[count]位置，不同元素多了一个，给count++
            3. 循环结束后，返回count
*/

    class Solution {
        public int removeDuplicates(int[] nums) {
            int count = 1;   // 标记从前往后遍历时，遇到的不同元素的个数
            for(int i = 1; i < nums.length; ++i){
                // 注意：count是从前往后遍历时遇到的不同元素的个数
                //       count-1就是i位置之前最后一个不同元素的位置
                // 因此需要将num[i]搬移到nums[count]处
                if(nums[count-1] != nums[i]){
                    nums[count++] = nums[i];
                }
            }

            return count;
        }
    }






























    class Solution {
        /*
          解题思路：
             1. 从前往后遍历nums，找到val第一次出现的位置
             2. 将val之后的所有元素整体往前搬移，即删除该val
             3. nums中有效元素个数减少一个
          循环进行上述操作，直到nums中所有值为val的元素全部删除完
          时间复杂度:O(N^2)  空间复杂度:O(1)
         */
        public int removeElement1(int[] nums, int val) {
            int size = nums.length;
            int i = 0;
            while(true){
                // 1. 在nums中找val的位置
                for(i = 0; i < size; ++i){
                    if(nums[i] == val){
                        break;
                    }
                }

                if(i == size){
                    // nums中没有发现值为val的元素，直接跳出while
                    break;
                }

                // 2. 将i位置之后所有元素整体往前搬移一个位置
                for(int pos = i+1; pos < size; ++pos){
                    nums[pos-1] = nums[pos];
                }

                // 注意：一趟之后size一定要减去1，因为删除了一个val
                size--;
            }
            return size;
        }


        /*
            解题思路:
              1. 创建一个长度与nums相同的数组ret
              2. 遍历nums，将nums中所有与val不同的元素搬移到ret中
              3. 将ret中所有元素拷贝回nums中


            时间复杂度: O(N)  空间复杂度: O(N)
        */
        public int removeElement2(int[] nums, int val) {
            int[] ret = new int[nums.length];
            int size = 0;
            for(int i = 0; i < nums.length; ++i){
                if(nums[i] != val){
                    ret[size++] = nums[i];
                }
            }

            System.arraycopy(ret, 0, nums, 0, size);
            return size
        };

        /*
           解题思路:
             1. 设置一个变量count，用来记录nums中值等于val的元素的个数
             2. 遍历nums数组，对于每个元素进行如下操作：
                  a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
                  b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
                     因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
                     因此次数需要将nums[i]往前搬移
             3. 返回删除之后新数组中有效元素个数

           时间复杂度：O(N)   空间复杂度：O(1)
        */
        public int removeElement(int[] nums, int val) {
            int count = 0;
            for(int i = 0; i < nums.length; ++i){
                if(nums[i] == val){
                    count++;
                }else{
                    nums[i - count] = nums[i];
                }
            }

            return nums.length - count;
        }
    }
}
